﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms.Implementation.ComparisonSorts
{
    public class QuickSort : Algorithm
    {
        protected override void ExecuteAlgorithm(int indexStart, int indexEnd)
        {
            if (indexStart < indexEnd)
            {
                int centerPoint = Divide(indexStart, indexEnd);

                if (centerPoint == indexStart)
                {
                    ExecuteAlgorithm(centerPoint + 1, indexEnd);
                }
                else if (centerPoint == indexEnd)
                {
                    ExecuteAlgorithm(indexStart, centerPoint - 1);
                }
                else
                {
                    ExecuteAlgorithm(indexStart, centerPoint - 1);
                    ExecuteAlgorithm(centerPoint + 1, indexEnd);
                }
            }
        }

        private int Divide(int indexStart, int indexEnd)
        {
            int indexCurrent = indexStart;
            int temp = 0;

            for (int i = indexStart; i < indexEnd; i++)
            {
                if (_sampleData[i] < _sampleData[indexEnd])
                {
                    if (i == indexCurrent)
                    {
                        indexCurrent++;
                        continue;
                    }
                    else
                    {
                        temp = _sampleData[indexCurrent];
                        _sampleData[indexCurrent] = _sampleData[i];
                        _sampleData[i] = temp;
                        indexCurrent++;
                    }
                }
            }

            if (indexCurrent < indexEnd)
            {
                temp = _sampleData[indexCurrent];
                _sampleData[indexCurrent] = _sampleData[indexEnd];
                _sampleData[indexEnd] = temp;
            }

            return indexCurrent;
        }
    }
}
